package com.jjlin.chapter_3;

import java.util.*;
public class CD165{
    //二叉树节点
    public static class ListNode{
        public int id;//编号
        public int val;//数值
        public ListNode left;//左孩子
        public ListNode right;//右孩子
        public ListNode(int id, int data){
            this.id = id;
            this.val = data;
        }
    }

    //建立二叉树
    public static ListNode createBinaryTree(int[][] nums, int root){
        if(nums == null || nums.length == 0 || nums[0] == null || nums[0].length == 0)
            return null;
        HashMap<Integer, ListNode> map = new HashMap<>();
        int len = nums.length;
        for(int i = 0; i < len; i++)
            map.put(nums[i][0], new ListNode(nums[i][0], nums[i][3]));

        for(int i = 0; i < len; i++){
            ListNode cur = map.get(nums[i][0]);
            cur.left = map.getOrDefault(nums[i][1], null);
            cur.right = map.getOrDefault(nums[i][2], null);
        }
        return map.get(root);
    }

    //在二叉树中找到累加和为指定数值的最长路径长度
    public static int getMaxLength(ListNode root, int sum){
        if(root == null)
            return 0;
        HashMap<Integer, Integer> map = new HashMap<>();//key存储的是从根节点到当前结点的路径的和sum，value存储的是sum出现的最早的层次
        map.put(0,0); //表示累加和为0的最早在0层就出现
        return preOrder(0, root, map, 1, sum, 0);
    }

    public static int preOrder(int preSum, ListNode node, HashMap<Integer, Integer> sumMap,
                               int level, int sum, int maxLen){
        if(node == null)
            return maxLen;
        int curSum = preSum + node.val;
        //当之前还没有出现过累加和为curSum的时候，加入map
        if(!sumMap.containsKey(curSum)){
            sumMap.put(curSum, level);
        }
        //当存在和为sum的路径时，记录最长路径的长度
        if(sumMap.containsKey(curSum - sum)){
            maxLen = Math.max(maxLen, level - sumMap.get(curSum - sum));
        }
        //继续查找左右子树
        maxLen = preOrder(curSum, node.left, sumMap, level + 1, sum, maxLen);
        maxLen = preOrder(curSum, node.right, sumMap, level + 1, sum, maxLen);
        //由于map中存放的是之前访问过的路径的和，以及他们对应的level，
        // 而如果在map中发现了curSum，且它的level不是上层，而且是当前这一层，那么说明curSum这个累加和的记录是在遍历到cur的时候加上去的
        //那么就需要将这个记录删除掉，免得后面使用它。因为它并不是代表的上层的多少个数的和值。
        if(sumMap.get(curSum) == level)
            sumMap.remove(curSum);
        return maxLen;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][4];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 4; j++)
                nums[i][j] = sc.nextInt();
        }
        int sum = sc.nextInt();
        ListNode head = createBinaryTree(nums, root);
        System.out.println(getMaxLength(head, sum));
    }
}
